package data_structure;

public class leetcode_0450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return root;
        if(root.val==key){
            if(root.left==null){
                return root.right;
            }
            else if(root.right==null){
                return root.left;
            }
            else{
                TreeNode node=root.left;
                while(node.right!=null) node=node.right;
                node.right=root.right.left;
                root.right.left=root.left;
                return root.right;
            }
        }
        TreeNode node=find(root,key);
        if(node==null) return root;
        if(node.val>key){
            deleteleft(node,node.left);
        }
        else{
            deleteright(node,node.right);
        }
        return root;

    }
    public TreeNode find(TreeNode node,int key){
        if(node==null) return null;
        if(node.left==null&&node.right==null) return null;
        if(node.left!=null&&node.left.val==key) return node;
        if(node.right!=null&&node.right.val==key) return node;
        if(node.val>key) return find(node.left,key);
        else return find(node.right,key);
    }
    public void deleteleft(TreeNode node1,TreeNode node2){
        if(node2.right==null){
            node1.left=node2.left;
            return;
        }
        else if(node2.left==null){
            node1.left=node2.right;
            return;
        }
        else{
            TreeNode node=node2.left;
            while(node.right!=null) node=node.right;
            node.right=node2.right.left;
            node2.right.left=node2.left;
            node1.left=node2.right;
        }
    }
    public void deleteright(TreeNode node1,TreeNode node2){
        if(node2.right==null){
            node1.right=node2.left;
            return;
        }
        else if(node2.left==null){
            node1.right=node2.right;
            return;
        }
        else{
            TreeNode node=node2.left;
            while(node.right!=null) node=node.right;
            node.right=node2.right.left;
            node2.right.left=node2.left;
            node1.right=node2.right;
        }
    }
}
